package com.sunny.l8;


public class Solution {

//    public static void main(String[] args) {
//
//        ListNode node1 = new ListNode(1);
//        ListNode node2 = new ListNode(2);
//        ListNode node3 = new ListNode(3);
//
//        node1.next = node2;
//        node2.next = node3;
//
//        Solution solution = new Solution();
//        solution.reorderList(node1);
//
//
//    }

    public void reorderList(ListNode head) {
        if(null == head || null == head.next)
            return;
        int len = getLen(head);
        int cnt = 0;
        int tmpInd = len>>1;
        ListNode p = head;
        if((len & 1) > 0) {
            while (cnt++ < tmpInd) {
                p = p.next;
            }
        }else{
            while (cnt++ < tmpInd-1) {
                p = p.next;
            }
        }
        ListNode tmpp = p;
        p = p.next;
        tmpp.next = null;

        ListNode rhead = reverse(p);

//        while (null!=rhead){
//            System.out.println(rhead.val);
//            rhead = rhead.next;
//        }
//
//        while (null != head){
//            System.out.println(head.val);
//            head = head.next;
//        }

        ListNode tmp = head;
        ListNode tmpz = head.next;
        while (null != rhead){
            tmp.next = rhead;
            rhead = rhead.next;
            tmp = tmp.next;
            if(null != tmpz) {
                tmp.next = tmpz;
                tmpz = tmpz.next;
                tmp = tmp.next;
            }
        }

//        print(head);
//        while (null != head){
//            System.out.println(head.val);
//            head = head.next;
//        }
    }

    public void print(ListNode head){
        ListNode p = head;
        while (null != p){
            System.out.print(p.val + " ");
            p = p.next;
        }
    }

    public ListNode reverse(ListNode head){

        ListNode p1 = null;
        ListNode p2 = head;
        if(null == p2)
            return p2;
        ListNode p3 = p2.next;

        while (null != p2){
            p2.next = p1;
            p1 = p2;
            p2 = p3;
            if(null != p3)
                p3 = p3.next;
        }

        return p1;
    }

    public int getLen(ListNode head){
        int res = 0;
        ListNode p = head;
        while (null != p){
            res++;
            p = p.next;
        }
        return res;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
      val = x;
      next = null;
    }
}
